/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/18
 * \* Time: 17:30
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 合并K个升序链表 {
    public class ListNode{
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 合并2个链表
     * @param a
     * @param b
     * @return
     */
    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if(a==null||b==null){
            return a==null?b:a;
        }

        ListNode head=new ListNode(0);
        ListNode tail=head,aPtr=a,bPtr=b;
        while (aPtr!=null&&bPtr!=null){
            if(aPtr.val< bPtr.val){
                tail.next=aPtr;
                aPtr=aPtr.next;
            }else {
                tail.next=bPtr;
                bPtr=bPtr.next;
            }
            tail=tail.next;
        }
        tail.next=(aPtr!=null?aPtr:bPtr);
        return head.next;
    }

    /**
     * 分治法合并k个链表
     * @param lists
     * @param l
     * @param r
     * @return
     */
    public ListNode merge(ListNode[]lists,int l,int r){
        if(l==r){
            return lists[l];
        }
        if(l>r){
            return null;
        }
        int mid=(r-l)/2+l;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));

    }

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0, lists.length-1);
    }
}